package com.chapter1.basic.analysis;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

/** 
 * @ClassName: Analysis 
 * @Description:  三个不同的数，和为0，求满足条件的数量
 * @author minjun minjun@bw30.com
 * @date 2015-2-12 下午5:02:34 
 *  
 */
public class Analysis {

	@Test
	public void test() throws Exception{
		
		int[] list=readPaper();
		
		long start=System.currentTimeMillis();
		
		int count=threeNum(list);
		
		long end=System.currentTimeMillis();
		System.out.println(count+",cost:"+(end-start)+"ms");
	}
	
	@Test
	public void testUF() {
//		QuickFind qf=new QuickFind(10);
//		QuickUnion qf=new QuickUnion(10);
//		QuickUnionImprove qf=new QuickUnionImprove(10);
		PathCompression qf=new PathCompression(10);
		qf.union(4, 3);
		qf.union(3, 8);
		qf.union(6, 5);
		qf.union(9, 4);
		qf.union(2, 1);
		qf.union(5, 0);
		qf.union(7, 2);
		qf.union(6, 1);
		qf.union(1, 0);
		qf.union(6, 7);
		
		System.out.println("connected :"+qf.getCount()+","+qf.connected(1, 0));
	}
	
	/** 
	* @Title: readPaper 
	* @Description: TODO(这里用一句话描述这个方法的作用) 
	* @param @return    设定文件 
	* @return char[]    返回类型 
	* @throws 
	*/ 
	private int[] readPaper() throws Exception{
		File file=new File("F:\\工具书\\-java实现-第四版-答案\\algs4-data\\algs4-data\\1Kints.txt");
		BufferedReader br=new BufferedReader(new FileReader(file));
		String line= null;
		List<Integer> list=new ArrayList<Integer>();
		while((line=br.readLine())!=null){
			if(!"".equals(line.trim())){
				list.add(Integer.parseInt(line.trim()));
			}
		}
		
		int[] array=new int[list.size()];
		
		for(int i=0;i<array.length;i++){
			array[i]=list.get(i);
		}
		
		return array;
	}

	/**
	 * 样本1000--时间393ms
	* @Title: threeNum 
	* @Description:(N^3) 
	* @param @param list
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws
	 */
	public int threeNum(int[] array){
		int len=array.length;
		int count=0;
		for(int i=0;i<len;i++){
			for(int j=i+1;j<len;j++){
				for(int m=j+1;m<len;m++){
					if(array[i]+array[j]+array[m]==0){
						count++;
					}
				}
			}
		}
		
		return count;
	}
	
	/**
	 *  样本1000--时间21ms
	* @Title: threeNumFast 
	* @Description: 利用二分法查找和快速排序共同优化处理了的三整数查找 N^2lgN
	* @param @param array
	* @param @return    设定文件 
	* @return int    返回类型 
	* @throws
	 */
	public int threeNumFast(int[] array){
		Arrays.sort(array);
		
		int len=array.length;
		int count=0;
		
		for(int i=0;i<len;i++){
			for(int j=i+1;j<len;j++){
				if(Arrays.binarySearch(array, -array[i]-array[j])>j){
					count++;
				}
			}
		}
		
		return count;
	}
	
}
